"""
给定一棵二叉树和两个目标节点p、q，找到它们的最近公共祖先（LCA：即同时是两个节点祖先且深度最大的节点）。
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor(root, p, q):
    """寻找二叉树中p和q的最近公共祖先（递归实现）"""
    # 递归终止条件：空节点或找到p/q（直接返回当前节点）
    if not root or root == p or root == q:
        return root
    # 递归左子树寻找p/q
    left_ancestor = lowest_common_ancestor(root.left, p, q)
    # 递归右子树寻找p/q
    right_ancestor = lowest_common_ancestor(root.right, p, q)
    # 左子树没找到，结果在右子树
    if not left_ancestor:
        return right_ancestor
    # 右子树没找到，结果在左子树
    if not right_ancestor:
        return left_ancestor
    # 左右子树各找到一个，当前节点就是LCA
    return root

def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    # 额外存储节点映射（用于快速获取p和q节点）
    node_map = {arr[0]: root}
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            node_map[arr[index]] = current.left
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            node_map[arr[index]] = current.right
            queue.append(current.right)
        index += 1
    return root, node_map

# 测试
# 树结构：
#       3
#      / \
#     5   1
#    / \ / \
#   6  2 0  8
#     / \
#    7   4
root, node_map = create_binary_tree([3,5,1,6,2,0,8,None,None,7,4])
p = node_map[5]
q = node_map[1]
print(lowest_common_ancestor(root, p, q).val)  # 输出: 3
p2 = node_map[5]
q2 = node_map[4]
print(lowest_common_ancestor(root, p2, q2).val)  # 输出: 5